package offer.question31_40.solutions;

public class QSolution40 {

    /*
     * 最小的 k 个数
     *
     * 这道题目需要使用分治法，等价于找到数组中第 k 小的数字。确切地说是快速排序对数组进行分割的思想。即首先在数组中随机选择一个数 val1，然后进行一轮快速排序，
     * 排序之后，在 val1 左边的数都是小于它的，在 val1 右边的数都是大于它的，其下标为 index1。
     *
     * 1.如果 index1 == k，那么就已经得到了数组中第 k 小的数；
     * 2.如果 index1 < k，那么数组中第 k 小的数在 [index1 + 1, N] 范围之中，那么前 index1 个数就不需要再进行检测了
     * 3.如果 index1 > k，那么数组中第 k 小的数在 [0, index1 - 1] 范围之中，那么 index1 后面的数就不再需要考虑了
     *
     * 时间复杂度为 O(logN)
     */

}
